README.md

669. Trim a Binary Search Tree

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

Example 1:

Input: 1 / \ 0 2 L = 1 R = 2 Output: 1 \ 2 

Example 2:

Input: 3 / \ 0 4 \ 2 / 1 L = 1 R = 3 Output: 3 / 2 / 1 

Solutions (Python)

1. Recursion

# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution: deftrimBST(self, root: TreeNode, L: int, R: int) ->TreeNode: ifnotroot: returnrootelifroot.val>R: returnself.trimBST(root.left, L, R) elifroot.val<L: returnself.trimBST(root.right, L, R) else: root.left=self.trimBST(root.left, L, R) root.right=self.trimBST(root.right, L, R) returnroot